import java.util.*;

class Solution2 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals.length == 0) {
            int[][] result = new int[1][];
            result[0] = newInterval;
            return result;
        }
        List<int[]> list = new ArrayList<>();
        for(int i = 0; i < intervals.length; i++) {
            if(newInterval == null) {
                list.add(intervals[i]);
                continue;
            }
            //||()
            if(intervals[i][0] > newInterval[1]) {
                list.add(newInterval);
                list.add(intervals[i]);
                newInterval = null;
            }else if(intervals[i][1] < newInterval[0]) {
                //()||
                list.add(intervals[i]);
                if(i == intervals.length - 1) {
                    list.add(newInterval);
                }
            }else if(intervals[i][0] < newInterval[0] && intervals[i][1] > newInterval[1]) {
                //(||)
                list.add(intervals[i]);
                newInterval = null;
            }else if(intervals[i][0] >= newInterval[0] && intervals[i][1] >= newInterval[1]) {
                //|(|)
                int[] tmp = new int[2];
                tmp[0] = newInterval[0];
                tmp[1] = intervals[i][1];
                list.add(tmp);
                newInterval = null;
            }else if(intervals[i][0] < newInterval[0] && intervals[i][1] <= newInterval[1]) {
                //(|)|
                int[] tmp = new int[2];
                tmp[0] = intervals[i][0];
                tmp[1] = newInterval[1];
                newInterval = tmp;
                if(i == intervals.length - 1) {
                    list.add(tmp);
                }
            }else if(intervals[i][0] >= newInterval[0] && intervals[i][1] < newInterval[1]) {
                //|()|
                if(i == intervals.length - 1) {
                    list.add(newInterval);
                }
            }else {
                System.out.println("no think");
                System.out.println(i);
            }
        }
        return toArray(list);
    }
    int[][] toArray(List<int[]> list) {
        int[][] result = new int[list.size()][];
        for(int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}